package CriticalPath;

import lombok.AllArgsConstructor;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * <p>关键路径</p>
 * <p>大白话讲其实就是最长路</p>
 * <p>具体实现方式主要有两种，在《数据结构》这门课程以及考研408中我们使用的都是拓扑排序方式所以在这里仅展示拓扑排序</p>
 * <p>感兴趣的同学可以在课下自己实现一下使用dijkstra实现关键路径，其实也不难（这里稍微提示一下，权值取反~，是不是突然就有思路了呢）</p>
 *
 * @author 没天赋
 * @since 2025-03-26
 */
@SuppressWarnings("all") // 作者有强迫症才标的注解不用管
public class CriticalPath {
    // 这里一大堆和拓扑排序没有区别，因为关键路径说白了也是kahn算法搞的，大家仔细阅读自己体会和拓扑的异同
    @AllArgsConstructor // 懒得写有参构造了，初学者还是建议写一下哈
    static class edge {
        int to, next, val;
    }
    public static final int N = (int) (1e5 + 5);
    public static edge[] edges = new edge[N];
    public static int[] head = new int[N];
    public static Queue<Integer> queue = new LinkedList<>();
    public static int[] in = new int[N];
    // 边权
    public static int[] dis = new int[N];
    //点数n，边数m,下标id（记录边数）,入度u，出度v，边权，记录进入拓扑序的点数
    public static int n, m, id, u, v, w, num;
    public static Scanner sc = new Scanner(System.in);

    // 注：这里我们默认起点是1，重点是n，其实哪个点开始结束都一样这里只是为了书写方便偷个小懒
    public static void main(String[] args) {
        n = sin();
        m = sin();
        for (int i = 0; i < m; i++) {
            u = sin();
            v = sin();
            w = sin();
            add(u, v, w);
        }
        //开始kahn算法
        if (kahn()) {
            //如果其中无环，输出关键路径长度
            System.out.println(dis[n]);
        } else {
            //如果有环，输出有环
            System.out.println("有环");
        }
    }

    public static boolean kahn() {
        //遍历入度，如果入度为0，则入队列
        for (int i = 1; i <= n; i++) {
            if (in[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            //出队列，并记录进入拓扑序的点数
            Integer temp = queue.poll();
            num++;
            //遍历临边，临边入度-1
            for (int i = head[temp]; i != 0; i = edges[i].next) {
                int x = edges[i].to;
                dis[x] = Math.max(dis[x], dis[temp] + edges[i].val);
                in[x]--;
                //如果入度为0，则入队列
                if (in[x] == 0) {
                    queue.add(x);
                }
            }
        }
        //如果进入拓扑序的点数等于点数，则无环，否则有环（这里不理解的同学可以动手画一画，画出来就不难理解啦）
        return num == n;
    }

    /**
     * 增边
     *
     * @param x
     * @param y
     * @param z
     */
    public static void add(int x, int y, int z) {
        id++;
        edges[id] = new edge(y, head[x], z);
        in[y]++;
        head[x] = id;
    }

    /**
     * 读取整数方法
     *
     * @return
     */
    public static int sin() {
        return sc.nextInt();
    }
}
/**
 * 测试数据：
 * 8 9
 * 1 2 3
 * 1 3 1
 * 2 4 2
 * 3 4 3
 * 4 5 1
 * 4 7 5
 * 5 6 2
 * 6 8 3
 * 7 8 5
 * --------
 * 15
 */